package cn.bellychang.bobo.binarysearch;

/**
 * @author ChangLiang
 * @date 2021/2/2
 */
public class SearchUtil {

    enum SearchAlgorithm {
        /**
         * 二分查找 递归方式
         */
        binarySearchRecursive,
        /**
         * 二分查找 非递归方式
         */
        binarySearchLoop,
        /**
         * linear search 寻求大于target的最小值的索引是什么
         */
        upperLinearSearch,
        /**
         * 递归方式 寻求大于target的最小值的索引是什么
         */
        upperSearchRecursive,
        /**
         * 递归方式 寻求小于target的最大值的索引是什么
         */
        lowerSearchRecursive,
        /**
         * 查找第一个值等于给定值的元素索引
         * 不存在，则返回-1
         */
        firstBinarySearch,
        /**
         * 查找最后一个值等于给定值的元素索引
         * 不存在，则返回-1
         */
        lastBinarySearch,
        /**
         * 查找第一个大于等于给定值的元素
         */
        upperFloor,
        /**
         * 查找最后一个小于等于给定值的元素
         */
        lowerCeil,
        /**
         * >=target
         * 如果target在data[]中存在，则返回最大索引
         * 如果target在data[]中不存在，则返回upper
         */
        upperCeil,
        /**
         * <=target
         * 如果target在data[]中存在，则返回最小索引
         * 如果target在data[]中不存在，则返回lower
         */
        lowerFloor,
    }

    public static <E extends Comparable<E>> int search(E[] data, E target, String searchAlgorithm) {
        if (searchAlgorithm.equals(SearchAlgorithm.binarySearchRecursive.name())) {
            return binarySearchRecursive(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.binarySearchLoop.name())) {
            return binarySearchLoop(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.upperLinearSearch.name())) {
            return upperLinearSearch(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.upperSearchRecursive.name())) {
            return upperSearchRecursive(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.lowerSearchRecursive.name())) {
            return lowerSearchRecursive(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.firstBinarySearch.name())) {
            return firstBinarySearch(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.lastBinarySearch.name())) {
            return lastBinarySearch(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.upperFloor.name())) {
            return upperFloorSearch(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.lowerCeil.name())) {
            return lowerCeilSearch(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.upperCeil.name())) {
            return upperCeilSearch(data, target);
        } else if (searchAlgorithm.equals(SearchAlgorithm.lowerFloor.name())) {
            return lowerFloorSearch(data, target);
        } else {
            throw new RuntimeException(searchAlgorithm + " is not supported now");
        }
    }

    private static <E extends Comparable<E>> int lowerFloorSearch(E[] data, E target) {
        if (data.length == 0 || data[0].compareTo(target) > 0) {
            return -1;
        }
        int l = 0;
        int r = data.length - 1;
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);
            if (data[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else if (data[mid].compareTo(target) < 0) {
                l = mid;
            } else {
                // 相等的情况 第一个元素 或者 前一个元素更小
                if (mid == l || data[mid - 1].compareTo(target) < 0) {
                    return mid;
                } else {
                    r = mid - 1;
                }
            }
        }
        return l;
    }

    private static <E extends Comparable<E>> int upperCeilSearch(E[] data, E target) {
        if (data.length == 0 || data[data.length - 1].compareTo(target) < 0) {
            return -1;
        }

        int l = 0;
        int r = data.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else if (data[mid].compareTo(target) > 0) {
                r = mid;
            } else {
                // 相等的情况，最后一个 或者 下一个 大于target
                if (mid == r || data[mid + 1].compareTo(target) > 0) {
                    return mid;
                } else {
                    l = mid + 1;
                }
            }
        }
        return l;
    }

    private static <E extends Comparable<E>> int lowerCeilSearch(E[] data, E target) {

        if (data.length == 0) {
            return -1;
        }
        if (data[0].compareTo(target) > 0) {
            return -1;
        }

        int l = 0;
        int r = data.length - 1;
        while (l < r) {
            int mid = l + ((r - l + 1) >> 1);
            if (data[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                // data[mid]<=target
                l = mid;
            }
        }
        return l;
    }

    private static <E extends Comparable<E>> int upperFloorSearch(E[] data, E target) {
        if (data.length == 0) {
            return -1;
        }

        // 所有元素都比target小
        if (data[data.length - 1].compareTo(target) < 0) {
            return -1;
        }

        int l = 0;
        int r = data.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return r;
    }

    private static <E extends Comparable<E>> int lastBinarySearch(E[] data, E target) {
        int l = 0;
        int r = data.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else if (data[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else {
                // 考虑是否是最后一个 以及后一个是否为target
                if (mid == r || data[mid + 1].compareTo(target) > 0) {
                    return mid;
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }

    private static <E extends Comparable<E>> int firstBinarySearch(E[] data, E target) {
        int l = 0;
        int r = data.length - 1;
        while (l <= r) {
            int mid = ((r - l) >> 1) + l;
            if (data[mid].compareTo(target) > 0) {
                r = mid - 1;
            } else if (data[mid].compareTo(target) < 0) {
                l = mid + 1;
            } else {
                // 当两个相等的时候 要考虑其左侧有相等的情况
                // 要考虑边界条件 第一个
                if (mid == l || data[mid - 1].compareTo(target) < 0) {
                    return mid;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }


    private static <E extends Comparable<E>> int lowerSearchRecursive(E[] data, E target) {
        if (target.compareTo(data[0]) <= 0) {
            return -1;
        }
        return lowerSearchRecursive(0, data.length - 1, data, target);
    }

    private static <E extends Comparable<E>> int lowerSearchRecursive(int beginIndex, int endIndex, E[] data, E target) {
        if (beginIndex == endIndex) {
            return beginIndex;
        }
        if (beginIndex + 1 == endIndex) {
            if (data[endIndex].compareTo(target) >= 0) {
                return beginIndex;
            } else {
                return endIndex;
            }
        }
        int mid = (endIndex - beginIndex) / 2 + beginIndex;
        if (data[mid].compareTo(target) >= 0) {
            return lowerSearchRecursive(beginIndex, mid - 1, data, target);
        } else {
            return lowerSearchRecursive(mid, endIndex, data, target);
        }
    }

    private static <E extends Comparable<E>> int upperSearchRecursive(E[] data, E target) {
        if (target.compareTo(data[data.length - 1]) >= 0) {
            return -1;
        }
        return upperSearchRecursive(0, data.length - 1, data, target);
    }

    private static <E extends Comparable<E>> int upperSearchRecursive(int beginIndex, int endIndex, E[] data, E target) {
        if (beginIndex == endIndex) {
            return beginIndex;
        }
        int middle = (endIndex - beginIndex) / 2 + beginIndex;
        if (data[middle].compareTo(target) <= 0) {
            return upperSearchRecursive(middle + 1, endIndex, data, target);
        } else {
            return upperSearchRecursive(beginIndex, middle, data, target);
        }
    }

    /**
     * 这里认为data可以是无序的
     *
     * @param data
     * @param target
     * @param <E>
     * @return
     */
    private static <E extends Comparable<E>> int upperLinearSearch(E[] data, E target) {
        int index = -1;
        // 保留前一个值
        for (int i = 0; i < data.length; i++) {
            if (data[i].compareTo(target) > 0) {
                if (index == -1) {
                    index = i;
                } else {
                    if (data[i].compareTo(data[index]) < 0) {
                        index = i;
                    }
                }
            }
        }
        return index;
    }

    private static <E extends Comparable<E>> int binarySearchLoop(E[] data, E target) {
        int beginIndex = 0;
        int endIndex = data.length - 1;

        // loop invariant: 我们要查找的target还可能在[beginIndex, endIndex]范围内
        while (beginIndex <= endIndex) {
            int middle = (endIndex - beginIndex) / 2 + beginIndex;
            if (data[middle].compareTo(target) > 0) {
                endIndex = middle - 1;
            } else if (data[middle].compareTo(target) < 0) {
                beginIndex = middle + 1;
            } else {
                return middle;
            }

        }
        return -1;
    }

    private static <E extends Comparable<E>> int binarySearchRecursive(E[] data, E target) {
        return binarySearchRecursive(0, data.length - 1, data, target);
    }

    private static <E extends Comparable<E>> int binarySearchRecursive(int beginIndex, int endIndex, E[] data, E target) {
        // not found
        if (beginIndex > endIndex) {
            return -1;
        }

        // prevent Integer overflow
        int pivotIndex = (endIndex - beginIndex) / 2 + beginIndex;
        if (data[pivotIndex].compareTo(target) != 0) {
            if (data[pivotIndex].compareTo(target) < 0) {
                return binarySearchRecursive(pivotIndex + 1, endIndex, data, target);
            } else {
                return binarySearchRecursive(beginIndex, pivotIndex - 1, data, target);
            }
        }
        return pivotIndex;
    }
}
